프로그래머스 - n^2 배열 자르기

| Lv. 2 | 월간 코드 챌린지 시즌3

PS
python프로그래머스

문제 사이트

https://school.programmers.co.kr/learn/courses/30/lessons/87390

문제 간단 요약

입력

  • 배열 크기(n)
    • n x n 크기의 2차원 배열
    • 1 <= n<= 10^7
  • 구간(left, right)
    • 1차원 배열의 특정 구간을 의미하는 인덱스
    • 0 <= left <= right <= n^2
    • right - left < 10^5

출력

  • 2차원 배열로 만든 1차원 배열의 특정 구간을 출력하는 문제

조건

  1. 2차원 배열 채우기
    20260707062339151
  2. 1차원 배열 만들기
    20260707062412043
  3. 원하는 구간 추출하기
    20260707062525345

풀이

고려할 점

  • 2차원 배열을 생성해서 모두 넣기에는 너무 많음
    • n^2 은 최대 10^14 까지 가능하여 규칙을 찾아야 함

채워진 2차원 배열을 잘 살펴보면 규칙이 존재한다.

  • (0, 0): 1
  • (1, 3): 4
  • (2, 1): 3
  • (3, 3): 4
  • …
    행과 열 중에 큰 값에서 +1을 하면 해당 위치에 들어가는 숫자를 알 수 있다.

left부터 right까지 숫자를 올리면서 좌표로 치환하여 계산하면, 최대 10^5 만 반복하면 된다.

좌표값은 n으로 사이즈를 알고있으니 쉽게 구할 수 있다.

  • 행: i//n
  • 열: i%n
def solution(n, left, right):
    
    answer = []
    
    for i in range(left, right+1):
        answer.append(max(i//n, i%n)+1)
    
    return answer

AI’s comment

좋은 점

1 ) 배열을 만들지 않고 인덱스 → 좌표 → 값 규칙(max(행, 열)+1)만으로 계산해, n^2이 최대 10^14여도 right-left < 10^5번만 반복하는 최적 접근임
2 ) 시간·공간 모두 출력 크기에 비례(O(right-left))해 이 문제에서 더 줄일 여지가 없음

아쉬운 점

1 ) (가독성·파이썬다움) append 루프는 리스트 컴프리헨션으로 한 줄에 담는 게 더 관용적이고, 파이썬에선 반복 append 호출이 사라져 약간 더 빠름

answer = [max(i//n, i%n)+1 for i in range(left, right+1)]

2 ) (사소) i//n과 i%n은 몫·나머지를 따로 두 번 나누는 셈임. divmod로 한 번에 구하면 의도가 더 드러남 (성능 차이는 미미)

answer.append(max(i//n, i%n)+1)      # 수정 전
answer.append(max(divmod(i, n))+1)   # 수정 후 (divmod가 (몫, 나머지) 튜플을 반환)

다른 풀이

1 ) 컴프리헨션 + divmod
위 두 지적을 합친 형태 — 접근·복잡도는 원본과 동일하고 표현만 더 간결함

def solution(n, left, right):
    return [max(divmod(i, n)) + 1 for i in range(left, right + 1)]
    # 원본의 for/append 루프 → 컴프리헨션 한 줄, i//n·i%n → divmod로 통합